//
// Created by wenyaxi on 24-11-1.
//
#include <common.h>

class Solution {
public:
    int trap(vector<int> &height) {
        int area_accumulate = 0;
        list<pair<int, int> > stk;
        for (int i = 0; i < height.size(); i++) {
            while (!stk.empty() && stk.back().first <= height[i]) {
                int last_height= stk.back().first;
                stk.pop_back();
                if (!stk.empty()) {
                    auto [fst, snd] = stk.back();
                    int width = i - snd - 1;
                    int h = min(height[i], fst)-last_height;
                    area_accumulate += width * h;
                }
            }
            stk.emplace_back(height[i], i);
        }
        return area_accumulate;
    }
};

int main(int argc, char *argv[]) {
    Solution s;
    vector<int> v = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << s.trap(v) << endl;
    return 0;
}
